#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
typedef struct _stNode
{
    int m_i_data;
    int m_i_height;
    struct _stNode *pLeft,*pRight;
}Node;

int Height(Node*);
Node* InsertNode(Node*, int);
Node* RightTurn(Node*);
Node* LeftTrun(Node*);
Node* LeftRightTurn(Node*);
Node* RightLeftTrun(Node*);
Node* DeleteNode(Node*, int);
Node* Rotate(Node*);
int PrintTree(Node*);
int Max(int, int);
int DeleteTree(Node**);

int main(int argc, char** argv)
{
    //srand((unsigned int)time(NULL));
    Node* tree = NULL;
    int i = 0;
    for (i = 0; i < 64; i++)
    {
        //int x = rand();
        tree = InsertNode(tree, i);
    }
    PrintTree(tree);
    printf("Height = %d\n", Height(tree));
    for (i = 0; i < 32+16; i++)
    {
        //int x = rand();
        tree = DeleteNode(tree, i);
    }
    PrintTree(tree);
    printf("Height = %d\n", Height(tree));
	DeleteTree(&tree);

    return 0;
}

Node* InsertNode(Node* in_pnode, int in_i_data)
{
    if (NULL == in_pnode)
    {
        in_pnode = (Node*)malloc(sizeof(Node));
        in_pnode->m_i_data = in_i_data;
        in_pnode->m_i_height = 0;
        in_pnode->pLeft = in_pnode->pRight = NULL;
    }
    else if( in_i_data < in_pnode->m_i_data)
	{
		in_pnode->pLeft = InsertNode(in_pnode->pLeft, in_i_data);
		//    判断此时树是否平衡
		if (Height(in_pnode->pLeft) - Height(in_pnode->pRight) == 2)
		{
			if (in_i_data < in_pnode->pLeft->m_i_data)
			{
				in_pnode = RightTurn(in_pnode);
			}
			else
			{
				in_pnode = LeftRightTurn(in_pnode);
			}
		}
	}
	else if( in_i_data > in_pnode->m_i_data)
	{
		in_pnode->pRight = InsertNode(in_pnode->pRight, in_i_data);

		if (Height(in_pnode->pRight) -  Height(in_pnode->pLeft) == 2)
		{
			if (in_i_data > in_pnode->pRight->m_i_data)
			{
				in_pnode = LeftTrun(in_pnode);
			}
			else
			{
				in_pnode = RightLeftTrun(in_pnode);
			}
		}
	}

	in_pnode->m_i_height = Max(Height(in_pnode->pLeft), Height(in_pnode->pRight)) + 1;
    return in_pnode;
}

Node* RightTurn(Node* a)
{
    /**    右旋
    *      a           b
    *     /           / \
    *    b      =>   c   a
    *   /
    *  c
    */ 
    Node* b = a->pLeft;
    a->pLeft = b->pRight;
    b->pRight = a;
    //    调整高度
    a->m_i_height = Max(Height(a->pLeft), Height(a->pRight)) + 1;
    b->m_i_height = Max(Height(b->pLeft), a->m_i_height) + 1;

    return b;
}

Node* LeftTrun(Node* a)
{
    /**    左旋
    *   a             b
    *     \          / \
    *      b    =>  a   c 
    *       \ 
    *        c
    */ 
    Node* b = a->pRight;
    a->pRight = b->pLeft;
    b->pLeft = a;
    //    调整高度
    a->m_i_height = Max(Height(a->pLeft), Height(a->pRight)) + 1;
    b->m_i_height = Max(a->m_i_height, Height(b->pRight)) + 1;

    return b;
}

Node* LeftRightTurn(Node* a)
{
    /**    左-右旋 b<c<a
    *      a        a      c
    *     /        /      / \
    *    b    =>  c   => b   a
    *     \      / 
    *      c    b
    */ 
	a->pLeft = LeftTrun(a->pLeft);
    return RightTurn(a);
}

Node* RightLeftTrun(Node* a)
{
    /**    右-左旋 b<c<a
    *  a      a         c
    *   \      \       / \
    *    b =>   c  => a   b
    *   /        \ 
    *  c          b
    */ 
	a->pRight = RightTurn(a->pRight);
    return LeftTrun(a);
}

int Height(Node* in_pnode)
{
    if (NULL == in_pnode)
    {
        return -1;
    }
    return in_pnode->m_i_height;
}

int PrintTree(Node* in_pnode)
{
    if (NULL == in_pnode)
    {
        return -1;
    }
    static n = 0;
    PrintTree(in_pnode->pLeft);
    printf("[%d]-->height[%d]data[%d]\n", ++n,in_pnode->m_i_height, in_pnode->m_i_data);
    PrintTree(in_pnode->pRight);
}

int Max(int a, int b)
{
    return (a > b ? a : b);
}

int DeleteTree(Node** p)
{
	if (NULL == p || NULL == *p)
	{
		return -1;
	}
    DeleteTree(&((*p)->pLeft));
    DeleteTree(&((*p)->pRight));
    free(*p);
    *p = NULL;
	return 0;
}

Node* DeleteNode(Node* p_node, int i_data)
{
	if (NULL == p_node)
	{
		return NULL;
	}
	if(i_data == p_node->m_i_data)
	{
		if (NULL == p_node->pRight)//
		{
			Node* p_tmp = p_node;
			p_node = p_node->pLeft;
			free(p_tmp);
		}
		else
		{
			Node* p_tmp = p_node->pRight;
			while (NULL != p_tmp->pLeft)
			{
				p_tmp = p_tmp->pLeft;
			}
			p_node->m_i_data = p_tmp->m_i_data;
			p_node->pRight = DeleteNode(p_node->pRight, p_tmp->m_i_data);
			p_node->m_i_height = Max(Height(p_node->pLeft), Height(p_node->pRight)) + 1;
		}
		return p_node;
	}
	else if (i_data < p_node->m_i_data)
	{
		p_node->pLeft = DeleteNode(p_node->pLeft, i_data);
	}
	else
	{
		p_node->pRight = DeleteNode(p_node->pRight, i_data);
	}
	p_node->m_i_height = Max(Height(p_node->pLeft), Height(p_node->pRight)) + 1;
	if (NULL != p_node->pLeft)
	{
		p_node->pLeft = Rotate(p_node->pLeft);
	}
	if (NULL != p_node->pRight)
	{
		p_node->pRight = Rotate(p_node->pRight);
	}
	p_node = Rotate(p_node);
	return p_node;
}

Node* Rotate(Node* p_node)
{
	if (Height(p_node->pLeft) - Height(p_node->pRight) == 2)
	{
		if (Height(p_node->pLeft->pLeft) >= Height(p_node->pLeft->pRight))
		{
			p_node = RightTurn(p_node);
		}
		else
		{
			p_node = LeftRightTurn(p_node);
		}
	}
	if (Height(p_node->pRight) - Height(p_node->pLeft) == 2)
	{
		if (Height(p_node->pRight->pRight) >= Height(p_node->pRight->pLeft))
		{
			p_node = LeftTrun(p_node);
		}
		else
		{
			p_node = RightLeftTrun(p_node);
		}
	}
	return p_node;
}
